1. Field of the Invention
The present invention relates to random number generators and more specifically to true or non-deterministic random number generators.
2. Prior Art
Devices for generating what are called true or non-deterministic random numbers are well known in the art. Examples of true random generators using a low-frequency oscillator and a high-frequency oscillator are described in U.S. Pat. No. 4,641,102 (1987), U.S. Pat. No. 5,781,458 (1998) and U.S. Pat. No. 6,061,702 (2000).
A circuit for generating true random numbers using high- and low-frequency oscillators is described in detail in An LSI Random Number Generator (RNG), Proc. Advances in Cryptology, Conference on CRYPTO, 1984, by Fairfield, Mortenson and Coulthart. The circuit described therein uses a noise component in the low-frequency signal as the source of entropy.
None of the previously available random number generators or methods have disclosed any way of calculating or knowing the actual amount of entropy available in the generated random sequences. Some prior art suggests brute force approaches, wasting perhaps hundreds of bits of entropy for each output bit. Other prior art produces sequences with less than one bit of entropy per output bit. This is a mixed true—pseudorandom generator of indeterminate properties.
Authors have suggested methods of generating true random numbers using components normally available on personal computers. These include deriving entropy from keyboard stroke timing, computer mouse movements, and air turbulence in the hard disk drive. Some discussion of such methods is given, for example, in Randomness Recommendations for Security, 1994, by Eastlake, Crocker and Schiller, at a web site with the following address: http://www.ietf.org/rfc/rfc1750. txt?number=1750. While these methods may be a source of entropy, the generation rates are very low and intermittent. Some of these methods require the interaction of a human operator making them unsuitable for most practical uses of random numbers.
All true random number generators require a physical source of entropy to produce random numbers, as distinct from algorithmically generated pseudorandom numbers, which are deterministic by nature of their source. The requirement for a physical generator has limited the availability of high quality, true random numbers due to cost, size, power requirements or difficulty in interfacing with the user's equipment.
A significant limitation of prior true random number generators is the uncertainty in the actual entropy and quality of the random numbers produced. Direct testing of a random sequence does not assure universally acceptable results in all applications, as different types of defects may not show up in a certain set of tests. Also, direct testing may be impractical due to the large number of bits—hence time—required to test to the required level of significance.
Systems for scrambling bits or correcting defects in random number sequences are also known in the art. Examples of these are contained in U.S. Pat. Nos. 5,963,104 (1999) and 6,061,702 (2000). Randomness defect correction can also be accomplished by encryption methods, such as DES.
It is important to know that randomness defect correction, or bit scrambling, does not in any way add entropy to the output sequence. Only the actual number of bits of entropy input to any deterministic algorithm can be taken as true random output bits from such an algorithm.
Randomness defect correctors and bit scramblers generally do not have proven, theoretical properties, which has resulted in unknown or unpredictable properties and quality of the random sequences produced by them. Also, not knowing the true entropy content in a random sequence that is used in cryptographic applications may lead to vulnerability to attack, especially by a quantum computer when one becomes available.